#ifndef __RB_TREE_H__
#define __RB_TREE_H__
namespace Aurora
{
    // 枚举颜色
    enum Color
    {
        RED,
        BLACK
    };
    // 节点
    template <class T>
    struct RBTreeNode
    {
        T _data;
        RBTreeNode<T> *_pLeft;
        RBTreeNode<T> *_pRight;
        RBTreeNode<T> *_pParent;
        Color _col;
        RBTreeNode(const T &data)
            : _data(data), _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _col(BLACK)
        {
        }
    };
    // 请模拟实现红黑树的插入--注意：为了后序封装map和set，本文在实现时给红黑树多增加了一个头结点
    template <class T>
    class RBTree
    {
        typedef RBTreeNode<T> Node;

    public:
        RBTree()
        {
            _pHead = new Node(-1);
            _pHead->_pLeft = _pHead;
            _pHead->_pRight = _pHead;
            _pHead->_pParent = _pHead;
        }

        // 在红黑树中插入值为data的节点，插入成功返回true，否则返回false
        // 注意：为了简单起见，本次实现红黑树不存储重复性元素
        bool Insert(const T &data)
        {
            if (_pHead->_pParent == _pHead)
            {
                // 第一次插入
                Node *newnode = new Node(data);
                // 改变parent的指向
                newnode->_pParent = _pHead;
                _pHead->_pParent = newnode;
                // 改变颜色
                newnode->_col = BLACK;
                return true;
            }
            Node *cur = _pHead->_pParent;
            Node *parent = nullptr;
            while (cur)
            {
                if (cur->_data > data)
                {
                    parent = cur;
                    cur = cur->_pLeft;
                }
                else if (cur->_data < data)
                {
                    parent = cur;
                    cur = cur->_pRight;
                }
                else
                {
                    return false;
                }
            }
            // 申请红色节点并插入
            cur = new Node(data);
            cur->_col = RED;
            // 判断插在左边还是右边
            if (parent->_data > data)
            {
                parent->_pLeft = cur;
            }
            else if (parent->_data < data)
            {
                parent->_pRight = cur;
            }
            cur->_pParent = parent;
            // 调整
            // parent为红,grandfather为黑
            while (parent && parent->_col == RED)
            {
                // 计算grandfather
                Node *grandfather = parent->_pParent;
                // 判断parent节点在grandfather的左边还是右边
                if (grandfather->_pLeft == parent)
                {
                    // 计算uncle节点
                    Node *uncle = grandfather->_pRight;
                    // 如果uncle存在且为红,那么就单纯的变色
                    if (uncle && uncle->_col == RED)
                    {
                        // 将parent和uncle变黑,grandfather变红
                        parent->_col = uncle->_col = BLACK;
                        grandfather->_col = RED;
                        // 继续往上更新
                        cur = grandfather;
                        parent = cur->_pParent;
                    }
                    else // uncle不存在或者存在且为黑
                    {
                        if (parent->_pLeft == cur)
                        {
                            //      g
                            //   p    u
                            // c
                            // 右旋
                            RotateR(grandfather);
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else
                        {
                            //      g
                            //   p    u
                            //      c
                            // 双旋
                            RotateL(grandfather->_pLeft);
                            RotateR(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                }
                else if (grandfather->_pRight == parent)
                {
                    // 计算uncle节点
                    Node *uncle = grandfather->_pLeft;
                    // 如果uncle存在且为红,就单纯改变颜色
                    if (uncle && uncle->_col == RED)
                    {
                        // 将parent和uncle变黑,grandfather变红
                        parent->_col = uncle->_col = BLACK;
                        grandfather->_col = RED;
                        // 继续往上更新
                        cur = grandfather;
                        parent = cur->_pParent;
                    }
                    else // uncle不存在或者存在且为黑
                    {
                        if (parent->_pRight == cur)
                        {
                            //    g
                            // u     p
                            //          c
                            // 左单旋
                            RotateL(grandfather);
                            parent->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        else
                        {
                            //    g
                            // u      p
                            //    c
                            // 双旋
                            RotateR(grandfather->_pRight);
                            RotateL(grandfather);
                            cur->_col = BLACK;
                            grandfather->_col = RED;
                        }
                        break;
                    }
                }
                else
                    break;
            }
            _pHead->_pParent->_col = BLACK;
            _pHead->_pLeft = LeftMost();
		    _pHead->_pRight = RightMost();
            return true;
        }

        // 检测红黑树中是否存在值为data的节点，存在返回该节点的地址，否则返回nullptr
        Node *Find(const T &data)
        {
            Node *cur = GetRoot();
            if(cur == _pHead) return nullptr;
            while(cur)
            {
                if(cur->_data > data)
                {
                    cur = cur->_pLeft;
                }
                else if(cur->_data < data)
                {
                    cur = cur->_pRight;
                }
                else
                {
                    return cur;
                }
            }
            return nullptr;
        }

        // 获取红黑树最左侧节点
        Node *LeftMost()
        {
            Node *cur = GetRoot();
            if(cur == _pHead) return nullptr;
            Node *parent = nullptr;
            while (cur)
            {
                parent = cur;
                cur = cur->_pLeft;
            }
            if (parent != nullptr)
                return parent;
            return _pHead;
        }

        // 获取红黑树最右侧节点
        Node *RightMost()
        {
            Node *cur = GetRoot();
            if(cur == _pHead) return nullptr;
            Node *parent = nullptr;
            while (cur)
            {
                parent = cur;
                cur = cur->_pRight;
            }
            if(parent != nullptr)
                return parent;
            return _pHead;
        }

        // 检测红黑树是否为有效的红黑树，注意：其内部主要依靠_IsValidRBTRee函数检测
        bool IsValidRBTRee()
        {
            if (GetRoot() == nullptr)
                return true;
            if (GetRoot()->_col == RED)
                return false;
            // 求最左路径的黑色节点
            size_t blackCount = 0;
            Node *cur = GetRoot();
            while (cur)
            {
                if (cur->_col == BLACK)
                    blackCount++;
                cur = cur->_pLeft;
            }
            return _IsValidRBTRee(GetRoot(), blackCount, 0);
        }
    private:
        bool _IsValidRBTRee(Node *pRoot, size_t blackCount, size_t pathBlack)
        {
            if (pRoot == nullptr)
            {
                if (blackCount != pathBlack)
                {
                    std::cout << "出现两条路径黑色节点不一样" << std::endl;
                    return false;
                }
                return true;
            }
            if (pRoot->_col == RED && pRoot->_pParent->_col == RED)
            {
                std::cout << "出现连续的红色节点" << std::endl;
                return false;
            }
            if (pRoot->_col == BLACK)
                pathBlack++;
            return _IsValidRBTRee(pRoot->_pLeft, blackCount, pathBlack) && _IsValidRBTRee(pRoot->_pRight, blackCount, pathBlack);
        }
        // 左单旋
        void RotateL(Node *pParent)
        {
            Node *subR = pParent->_pRight;
            Node *subRL = subR->_pLeft;
            // 记录parent节点
            Node *parent = pParent->_pParent;
            // 调整
            pParent->_pRight = subRL;
            subR->_pLeft = pParent;
            // 修改每个节点的parent指针
            pParent->_pParent = subR;
            if (subRL)
                subRL->_pParent = pParent;
            // 判断是否为根节点
            if (_pHead->_pParent == pParent)
            // if(parent == _pHead)
            {
                _pHead->_pParent = subR;
                subR->_pParent = _pHead;
            }
            else
            {
                if (parent->_pLeft == pParent)
                {
                    parent->_pLeft = subR;
                }
                else if (parent->_pRight == pParent)
                {
                    parent->_pRight = subR;
                }
                subR->_pParent = parent;
            }
        }
        // 右单旋
        void RotateR(Node *pParent)
        {
            Node *subL = pParent->_pLeft;
            Node *subLR = subL->_pRight;
            // 记录parent节点
            Node *parent = pParent->_pParent;
            // 调整
            pParent->_pLeft = subLR;
            subL->_pRight = pParent;
            // 修改节点的parent的指针
            pParent->_pParent = subL;
            if (subLR)
                subLR->_pParent = pParent;
            if (_pHead->_pParent == pParent)
            // if(_pHead == parent)
            {
                _pHead->_pParent = subL;
                subL->_pParent = _pHead;
            }
            else
            {
                if (parent->_pLeft == pParent)
                {
                    parent->_pLeft = subL;
                }
                else if (parent->_pRight == pParent)
                {
                    parent->_pRight = subL;
                }
                subL->_pParent = parent;
            }
        }
        // 为了操作树简单起见：获取根节点
        Node *&GetRoot()
        {
            return _pHead->_pParent;
        }

    private:
        Node *_pHead;
    };
}

#endif